//题目要求：
//给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
//请你将两个数相加，并以相同形式返回一个表示和的链表。
//你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

//示例1：
// 输入：l1 = [2,4,3], l2 = [5,6,4]
// 输出：[7,0,8]
// 解释：342 + 465 = 807.
//示例2：
// 输入：l1 = [0], l2 = [0]
// 输出：[0]
//示例3：
// 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
// 输出：[8,9,9,9,0,0,0,1]

// 提示：
// 每个链表中的节点数在范围 [1, 100] 内
// 0 <= Node.val <= 9
// 题目数据保证列表表示的数字不含前导零

#include <stdio.h>
#include<stdlib.h>

struct ListNode{
    int val;
    struct ListNode *next;
};

void creat_ListNode(struct ListNode* l,int* arr,int sz)
{
    for(int i = 0;i<sz;i++)
    {
        l->val = arr[i];
        if(i!=sz-1)
        {
            l->next = l+1;
            l++;
        }
        else
        {
            l->next = NULL;
        }
    }
}

void print_ListNode(struct ListNode* l)
{
    while(l!=NULL)
    {
        printf("%d ",l->val);
        l=l->next;
    }
    printf("\n");
}

int cal_ListNode_size(struct ListNode* l)
{
    int tmp = 0;
    while(l!=NULL)
    {
        tmp++;
        l = l->next;
    }
    return tmp;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *head = NULL, *tail = NULL;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;
        if (!head) {
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        } else {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = sum / 10;//新的进位值
        if (l1) {
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }
    //遍历结束后，有进位大于0，附加一个值为carry的节点
    if (carry > 0) {
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }
    return head;
}


// struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
// {
//     int sz1 = cal_ListNode_size(l1);
//     int sz2 = cal_ListNode_size(l2);
//     int sz = sz1>sz2?sz1:sz2;
//     struct ListNode* ret = malloc(sizeof(struct ListNode)*(sz+1));
//     struct ListNode* result = ret;
//     int flag = 0;
//     while(l1!=NULL && l2!=NULL)
//     {
//         int tmp = l1->val + l2->val + flag;
//         ret->val = tmp%10;
//         flag = 0;
//         if(tmp>=10)
//         {
//             flag = 1;
//         }
//         if(l1->next==NULL && l2->next==NULL && flag == 0)
//         {
//             ret->next = NULL;
//             return result;
//         }
//         else
//         {
//             ret->next = ret+1;
//         }
//         ret++;
//         l1 = l1->next;
//         l2 = l2->next;
//     }
    
//     if(l1!=NULL)
//     {
//         while(l1!=NULL)
//         {
//             int tmp = l1->val + flag;
//             ret->val = tmp%10;
//             flag = 0;
//             if(tmp>=10)
//             {
//                 flag = 1;
//             }
//             if(l1->next == NULL && flag == 0)
//             {
//                 ret->next = NULL;
//                 return result;
//             }
//             else
//             {
//                 ret->next = ret+1;
//             }
//             ret++;
//             l1 = l1->next;
//         }
//     }
//     if(l2!=NULL)
//     {
//         while(l2!=NULL)
//         {
//             int tmp = l2->val + flag;
//             ret->val = tmp%10;
//             flag = 0;
//             if(tmp>=10)
//             {
//                 flag = 1;
//             }
//             if(l2->next == NULL && flag == 0)
//             {
//                 ret->next = NULL;
//                 return result;
//             }
//             else
//             {
//                 ret->next = ret+1;
//             }
//             ret++;
//             l2 = l2->next;
//         }
//     }
    
//     ret->val = 1;
//     ret->next = NULL;
//     return result;
// }

int main()
{
    int arr1[] = {5,5,5,5,9,9,9};
    int arr2[] = {6,4,4,9};
    int size1 = sizeof(arr1)/sizeof(arr1[0]);
    int size2 = sizeof(arr2)/sizeof(arr2[0]);
    
    struct ListNode* l1 = malloc(sizeof(struct ListNode)*size1);
    struct ListNode* l2 = malloc(sizeof(struct ListNode)*size2);
    // for(int i = 0;i<size1;i++)
    // {
    //     l1->val = arr1[i];
    //     if(i!=size1-1)
    //     {
    //         l1->next = (++l1);
    //     }
    //     else
    //     {
    //         l1->next = NULL;
    //     }
    // }
    creat_ListNode(l1,arr1,size1);
    creat_ListNode(l2,arr2,size2);

    //验证是否创建单链表成功
    print_ListNode(l1);
    print_ListNode(l2);

    //验证计算链表长度函数的正确性
    // int l_size = cal_ListNode_size(l1);
    // printf("%d\n",l_size);

    //对两个单链表进行求和
    struct ListNode* sum;
    sum = addTwoNumbers(l1,l2);

    //输出求和结果进行验证
    print_ListNode(sum);

    return 0;
}